package com.spirng.leetcode.day04;

import java.util.Arrays;
import java.util.List;

public class String6 {
    public static void main(String[] args) {
//        strStr("sadbutsad","sad");
        int i = strStr("sadbutsad", "tsad");
        System.out.println(i);
    }
    public static int strStr(String haystack, String needle) {
        int[] next = creatNext(needle);
        char[] charArray = haystack.toCharArray();
        char[] charArray1 = needle.toCharArray();
        if(charArray1.length>charArray.length){
            return -1;
        }
        int j=0;
        for (int i= 0; i < charArray.length; i++) {
           while (j>0&&charArray1[j]!=charArray[i]){
               j=next[j-1];
           }
           if(charArray1[j]==charArray[i]){
               j++;
           }
           if(j==charArray1.length){
               return  (i-charArray1.length+1);
           }
        }
        return -1;
    }
    public static int []  creatNext(String s){
        int [] next=new int[s.length()];
        int j=0;//最大公共前后缀值 前缀最大值
        int i=0;//后缀最大值
        //初始化数组
        next[0]=j;
        char[] model = s.toCharArray();
        for ( i =1 ; i < s.length(); i++) {
            //不同
            while (j>0&&model[j] != model[i]) {
                j=next[j-1];
            }
            //前缀最大值和后缀最大值相同
            if(model[j]==model[i]) j++;
            next[i]=j;
        }
        return next;
    }
    public static int strStr1(String haystack, String needle) {
        if(needle.length()>haystack.length()){
            return -1;
        }
        char[] charArray = haystack.toCharArray();
        char[] charArray1 = needle.toCharArray();
        for (int i = 0; i < haystack.toCharArray().length; i++) {
            int length=charArray1.length-1;
            while (charArray[i] != charArray1[length]){
                i++;
            }
            while(i*length>=0&&charArray[i]==charArray1[length]){
                i--;
                length--;
                if(length<0){
                    return i+1;
                }
            }
        }
        return -1;
    }

}
